Belief propagation as a dynamical system: The linear case and open problems

Abstract

Systems and control theory have found wide application in the analysis and design of numerical algorithms. The authors present an equivalent discrete-time dynamical system interpretation of an algorithm commonly used in information theory called belief propagation (BP). BP is one instance of the so-called sum-product algorithm and arises, for example, in the context of iterative decoding of low-density parity-check codes. The authors review a few known results from information theory in the language of dynamical systems and show that the typically very high-dimensional, non-linear dynamical system corresponding to BP has interesting structural properties. For the linear case, they completely..